package binaryTree;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Node {
    public int val;
    public List<Node> children;
    public Node() {}
    public Node(int _val) {
        val = _val;
    }
    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
}
//N 叉树的最大深度
public class Ntree {
    public int maxDepth(Node root) {
        LinkedList<Node> nodes = new LinkedList<>();
        nodes.add(root);
        int  depth=0;
        while (!nodes.isEmpty()){
            depth++;
            int size = nodes.size();
            while (size>0){
                Node cur= nodes.poll();
                if (cur.children!=null){
                    for (int i = 0; i < cur.children.size(); i++)
                        if (cur.children.get(i) != null)
                            nodes.add(cur.children.get(i));
                }
                size--;
            }
        }
                return  depth;
    }


    public int maxDepth1(Node root) {
        if (root == null)   return 0;
        int depth = 0;
        Queue<Node> que = new LinkedList<>();
        que.offer(root);
        while (!que.isEmpty())
        {
            depth ++;
            int len = que.size();
            while (len > 0)
            {
                Node node = que.poll();
                for (int i = 0; i < node.children.size(); i++)
                    if (node.children.get(i) != null)
                        que.offer(node.children.get(i));
                len--;
            }
        }
        return depth;
    }


    /*递归法，后序遍历求root节点的高度*/
//    public int maxDepth(Node root) {
//        if (root == null) return 0;
//        int depth = 0;
//        if (root.children != null){
//            for (Node child : root.children){
//                depth = Math.max(depth, maxDepth(child));
//            }
//        }
//        return depth + 1; //中节点
//    }




}
